|
In probability theory, the birthday problem or birthday paradox〔This is not a paradox in the sense of leading to a logical contradiction, but is called a paradox because the mathematical truth contradicts naive intuition: an intuitive guess would suggest that the chance of two individuals sharing the same birthday in a group of 23 is much lower than 50%, but the birthday problem demonstrates that this is not the case.〕 concerns the probability that, in a set of randomly chosen people, some pair of them will have the same birthday. By the pigeonhole principle, the probability reaches 100% when the number of people reaches 367 (since there are 366 possible birthdays, including February 29). However, 99.9% probability is reached with just 70 people, and 50% probability with 23 people. These conclusions include the assumption that each day of the year (except February 29) is equally probable for a birthday. The history of the problem is obscure. W. W. Rouse Ball indicated (without citation) that it was first discussed by Harold Davenport.〔W. W. Rouse Ball, 1960, ''Other Questions on Probability'', in ''Mathematical Recreations and Essays, Macmillan', New York, p 45.〕 However, Richard von Mises proposed an earlier version of what is considered today to be the birthday problem.〔(The Birthday Problem )〕 The mathematics behind this problem led to a well-known cryptographic attack called the birthday attack, which uses this probabilistic model to reduce the complexity of finding a collision for a hash function. ==Understanding the problem== The birthday problem is to find the probability that, in a group of N people, there is at least one pair of people who have the same birthday. See "Same birthday as you" further for an analysis of the case of finding the probability of a given, fixed person having the same birthday as any of the remaining people. In the example given earlier, a list of 23 people, comparing the birthday of the first person on the list to the others allows 22 chances for a matching birthday, the second person on the list to the others allows 21 chances for a matching birthday (in fact the 'second' person also has total 22 chances of matching birthday with the others but his/her chance of matching birthday with the 'first' person, one chance, has already been counted with the first person's 22 chances and shall not be duplicated), third person has 20 chances, and so on. Hence total chances are: , so comparing every person to all of the others allows 253 distinct chances (combinations): in a group of 23 people there are distinct possible combinations of pairing. Presuming all birthdays are equally probable,〔In reality, birthdays are not evenly distributed throughout the year; there are more births per day in some seasons than in others, but for the purposes of this problem the distribution is treated as uniform. In particular, many children are born in the summer, especially the months of August and September (for the northern hemisphere) (), and in the U.S. it has been noted that many children are conceived around the holidays of Christmas and New Year's Day. Also, because hospitals rarely schedule C-sections and induced labor on the weekend, more Americans are born on Mondays and Tuesdays than on weekends; where many of the people share a birth year (e.g. a class in a school), this creates a tendency toward particular dates. In Sweden 9.3% of the population is born in March and 7.3% in November when a uniform distribution would give 8.3% (Swedish statistics board ). See also: * * These factors tend to increase the chance of identical birth dates, since a denser subset has more possible pairs (in the extreme case when everyone was born on three days, there would obviously be many identical birthdays). The problem of a non-uniform number of births occurring during each day of the year was first understood by Murray Klamkin in 1967. A formal proof that the probability of two matching birthdays is least for a uniform distribution of birthdays was given by D. Bloom (1973).〕 the probability of a given birthday for a person chosen from the entire population at random is 1/365 (ignoring February 29). Although the number of pairings in a group of 23 people is not statistically equivalent to 253 pairs chosen independently, the birthday problem becomes less surprising if a group is thought of in terms of the number of possible pairs, rather than as the number of individuals. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Birthday problem」の詳細全文を読む スポンサード リンク
|